//1.中间节点+递归

class Solution {
public:
    TreeNode* ActToBST(vector<int>& nums, int left, int right) {
        if(left > right) return nullptr;

        int mid = left+(right-left)/2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = ActToBST(nums, left, mid-1);
        root->right = ActToBST(nums, mid+1, right);

        return root;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return ActToBST(nums, 0, nums.size()-1);
    }
};